class SegTree(private var n: Int = 1e9.toInt()) {
    private class Node {
        var value = 0
        var lazy = 0
    }
    private val tree = hashMapOf<Int, Node>().withDefault { Node() }


    private fun pushUp(root: Int) {
        tree.getOrPut(root) { Node() } .value = maxOf(
            tree.getValue(root * 2).value,
            tree.getValue(root * 2 + 1).value
        )
    }

    private fun pushDown(root: Int) {
        if (tree.getOrPut(root) { Node() }.lazy != 0) {
            tree.getOrPut(root * 2) { Node() }.value = tree[root]!!.value
            tree[root * 2]!!.lazy = tree[root]!!.lazy
            tree.getOrPut(root * 2 + 1) { Node() }.value = tree[root]!!.value
            tree[root * 2 + 1]!!.lazy = tree[root]!!.lazy

            tree[root]!!.lazy = 0
        }
    }

    fun update(from: Int, to: Int, value: Int) {
        fun update(root: Int, left: Int, right: Int) {
            if (to < left || from > right) return
            if (from <= left && right <= to) {
                tree.getOrPut(root) { Node() }.value = value
                tree[root]!!.lazy = value
                return
            }
            pushDown(root)
            val mid = (right - left) / 2 + left
            update(root * 2, left, mid)
            update(root * 2 + 1, mid + 1, right)
            pushUp(root)
        }
        update(1, 1, n)
    }

    fun query(from: Int, to: Int): Int {
        fun query(root: Int, left: Int, right: Int): Int {
            if (to < left || from > right) return 0
            if (from <= left && right <= to) return tree.getOrPut(root) { Node() } .value
            pushDown(root)
            val mid = (right - left) / 2 + left
            return maxOf(
                query(root * 2, left, mid),
                query(root * 2 + 1, mid + 1, right)
            )
        }
        return query(1, 1, n)
    }
}


